/*  快速排序的建议
    1、记概念或者原理
    2、分人
        a、带入数据进去记住(数据小)
        b、类比for循环(由里到外)
        c、死记
*/


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE       10     // 内存元素的个数
#define RAND_NUM_RANGE  1000    // 随机数的获取范围


/**
  * @brief  交换两个数据
  * @note   默认整型数据(int、char等)
  * @param  num1：要交换数据1
  *         num2：要交换数据2
  * @retval None
  */
void QUICK_SORT_Swap(int *num1, int *num2)
{
    int tmp;        // 交换两个数据的中间值
    
    tmp   = *num1;  // 想一想装满可乐的瓶子想要倒进装满七喜的瓶子，应该怎么做？ 先拥有一个空瓶子 
    *num1 = *num2;
    *num2 = tmp;
}


/**
  * @brief  显示数据
  * @note   None
  * @param  data_p：指向要显示数据内存的指针
  *         len：   数据内存的长度
  * @retval None
  */
void QUICK_SORT_Show(int data_p[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf("%d  ", *(data_p+i));
    }
    printf("\n");
}


/**
  * @brief  获取随机数，并返回
  * @note   None
  * @param  size: rand函数随机数范围的最大值
  * @retval 返回获取得到的随机数
  */
int QUICK_SORT_Rand(int size)
{
    // 1、判断传进来的范围值，是否超出范围
    if(size > 32767)
        return -1;

    // 2、返回随机数
    return rand()%(size+1);
}



/**
  * @brief  快速排序
  * @note   None
  * @param  data_p：指向要排序的内存的指针
  *         len：   排序内存元素的个数
  * @retval None
  */
int QUICK_SORT_DataSort(int data_p[], int len)
{
    // 1、退出条件
    if(len <= 1)
        return 0;

    int i = 0;
    int j = len-1;      // 2、不断递进的过程

    // 这里是为了找到支点，以方便传给下一次递归
    while (i<j)
    {
		// 从右向左比较，顺序j--，逆序交换
        while( (data_p[i] <= data_p[j]) && (i<j) )	
		{
            j--;								
		}
        QUICK_SORT_Swap(&data_p[i], &data_p[j]); 

        // 从左向右比较，顺序i++，逆序交换
        while( (data_p[i] <= data_p[j]) && (i<j))	
		{

            i++;								
		}
        QUICK_SORT_Swap(&data_p[i], &data_p[j]);  
    }

    // 3、不断逼进结果
    int num = QUICK_SORT_DataSort(data_p, i);	        // 解决左边序					         			
    QUICK_SORT_DataSort(data_p + num+1, len-num-1);     // 解决右边序

}




int main(int argc, char const *argv[])
{
    // 0、我们是伪随机，所以需要有一个随时变化的种子(时间)
    srand(time(NULL));              

    // 1、随机生成数据
    int data_buf[DATA_SIZE] = {0};
    for (int i = 0; i < DATA_SIZE; i++)
    {
        data_buf[i] =  QUICK_SORT_Rand(RAND_NUM_RANGE);
    }
    
    // 2、打印生成的随机数据(原数据)
    printf("原数据：\n");
    QUICK_SORT_Show(data_buf, DATA_SIZE);

    printf("排序后的数据：\n");
    QUICK_SORT_DataSort(data_buf, DATA_SIZE);
    QUICK_SORT_Show(data_buf, DATA_SIZE);
    
    return 0;
}


